package codeTop;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * q395
 *
 * @author 雨凡
 * @version q395.java, v0.1
 * @date 2025/07/04/13:08
 */
public class q395 {
    public int longestSubstring(String s, int k) {
        return dfs(s,k,0,s.length()-1);
    }
    int dfs(String s,int k,int l, int r){
        if (r-l+1<k) {
            return 0;
        }
        Map<Character,Integer> map = new HashMap<>();
        for (int i = l; i <= r; i++) {
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }
        Set<Character> set = map.keySet().stream().filter(key -> map.get(key) < k).collect(Collectors.toSet());
        if (set.isEmpty()) {
            return r-l+1;
        }else {
            int max = 0;
            for (int i = l; i <= r ; i++) {
                if (set.contains(s.charAt(i))) {
                    int num1 = dfs(s, k, l, i - 1);
                    int num2 = dfs(s, k, i + 1, r);
                    max = Math.max(max,Math.max(num1,num2));
                    break;
                }
            }
            return max;
        }
    }

    public static void main(String[] args) {
        q395 q = new q395();
        System.out.println(q.longestSubstring("bbaaacbd", 3));
    }
}
